The invention relates to a cryptographic method protected against attacks of the covert channel type. The invention is in particular advantageous for protecting algorithms during which a block of instructions from amongst several different blocks of instructions is executed as a function of an input variable. Such an algorithm is for example, but not limitingly, a binary exponentiation algorithm performing a calculation of the type B=AD, with A, B and D being integer numbers. Such an algorithm is for example implemented in electronic devices such as chip cards.
The outline diagram of such an algorithm is depicted in FIG. 1. It comprises a first step of testing the value of an input data item. According to the result of the test, a block of instructions Π0 or a block of instructions Π1 is carried out. The algorithm can then terminate, or a new test step is performed on another input variable. In the example of an operation of the type B=AD, the input variable is a bit Di of D and the diagram in FIG. 1 is repeated successively for each bit of D.
The blocks of instructions Π0, Π1 each comprise a set of instructions to be executed, for example operations of addition, multiplication, variable updating, etc. The number and/or the type of instruction may be different from one block of instructions Π0, Π1 to the other.
Many cryptographic algorithms are based on the outline diagram in FIG. 1. This is in particular the case with cryptographic algorithms based on exponentiation calculations of the type B=AD, where A, B are integer numbers usually of large size, and D a predetermined number of M bits.
The numbers A, B may correspond for example to a text which is enciphered or to be enciphered, a data item which is signed or to be signed, a data item which is verified or to be verified, etc. The number D may correspond to elements of keys, private or public, used for enciphering or deciphering the numbers A, B.
By way of example of the algorithms such as the so-called “Square-And-Multiply” algorithm, the so-called “Right-To-Left binary algorithm” and the so-called “(M, M3) algorithm” may be used for performing exponentiation calculations.
A malevolent user may possibly undertake attacks aimed at discovering in particular confidential information (such as for example the key D or a data item derived from this key) manipulated in processings carried out by the calculation device executing an exponentiation operation.
A simple attack, known as a “timing attack”, against the algorithm in FIG. 1 consists in measuring the time necessary for the device to execute a block of instructions between two test steps. If the execution times for the blocks of instructions Π0, Π1 are different, then it is easy to identify a block of instructions Π0 or Π1 and to deduce therefrom the value of the associated input variable.
In order to protect against this attack, it is possible to add fictional instructions in the shortest block of instructions Π0 or Π1 (a block of instructions is “the shortest” if the time taken to perform it is the least) so that the two blocks of instructions Π0, Π1 are of the same duration.
An instruction is said to be fictional if its execution does not modify the data manipulated by the algorithm. For example, the instruction i←i−0 is a fictional instruction (i is here a loop variable and the notation “←” signifies incrementation, by zero here, of the loop variable).
Though this solution is effective against “timing attacks”, it is not effective against other types of covert channel attack and it may also be detrimental to the algorithm execution time.
The most widely known covert channel attacks are the so-called simple or differential ones. Covert channel attack means an attack based on a physical quantity measurable from outside the device and whose direct analysis (simple attack) or analysis according to a statistical method (differential attack) makes it possible to discover information manipulated in processings carried out in the device. For example, in a “timing attack”, the covert channel (the physical quantity measurable from the outside) is time.
Covert channel attacks can make it possible to discover confidential information. These attacks were in particular revealed by Paul Kocher (Advances in Cryptology—CRYPTO '99, Vol. 1666 of Lecture Notes in Computer Science, pp. 388-397, Springer-Verlag, 1999).
Amongst the physical quantities which can be exploited for these purposes, there can be cited the execution time, the current consumption, the electromagnetic field radiated by the part of the component used for executing the calculation, etc. These attacks are based on the fact that, during the execution of an algorithm, the manipulation of a bit, that is to say its processing by a particular instruction, leaves a particular imprint on the physical quantity in question, according to the value of this bit and/or according to the instruction.
Covert channel attacks may succeed with algorithms such as the one in FIG. 1 if the blocks of instructions Π0, Π1 are not equivalent vis-à-vis these attacks.
The term “equivalent” must be understood here and throughout the remainder of the text in the following manner. Two instructions INST1, INST2 (or two blocks of instructions Π0, Π1) are said to be equivalent (INST0 is denoted ˜INST1) if it is not possible to differentiate them by means of a covert channel attack. This is the case in particular if the physical quantity measured during the attack follows the same development for the two instructions. It should be noted however that two instructions may be equivalent vis-à-vis one covert channel attack and not be equivalent vis-à-vis another covert channel attack.
In the same way, it will be said that two instructions (or blocks of instructions) are equal if, when they are used with the same input data, they produce identical output data.
It is known how to protect against covert channel attacks by adding fictional instructions to the algorithm. It is assumed hereinafter that a fictional instruction is equivalent to a similar real instruction. For example, the instruction i←i−0 is assumed to be equivalent to the instruction i←i−1.
In the case of the algorithm in FIG. 1, it is thus known how to effect a fictional block of instructions Π1 after each block of instructions Π0, and to effect in a symmetrical manner a fictional block of instructions Π0 before each block of instructions Π1 (see the steps in dotted lines in FIG. 1). Thus, whatever the value of the input data item, a block of instructions Π0 and a block of instructions Π1 will be effected, in this order, one or other being fictional, so that it is not possible to predict the value of the input data item, the physical quantities relating to a calculation being equivalent. Thus there is denoted:(Π0∥Π1(fictional))˜(Π0(fictional)∥Π1).
The notation “∥” signifies the successive effecting of blocks of instructions Π0, Π1 (or more generally the successive effecting of two instructions).
Though this solution is effective against covert channel attacks, it does however have the drawback of multiplying on average by two the time needed for executing the algorithm.
This is because, in the case of an unprotected algorithm using M input data (for example the M bits of a data item D), statistically on average M/2 blocks of instructions Π0 and M/2 blocks of instructions Π1 are effected. If T0 and respectively T1 are the average times for executing a block of instructions Π0 or respectively Π1, then the average time for executing the unprotected algorithm is equal to M*(T0+T1)/2.
On the other hand, in the case of the algorithm protected by fictional blocks of instructions Π0, Π1, a block of instructions Π0 and a block of instructions Π1 are systematically effected for each of the M input data. Consequently the average time for executing the algorithm protected by fictional blocks of instructions is equal to M*(T0+T1).